package hot100;

import java.util.HashMap;
import java.util.Map;

public class Main {
    //https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked
    public int subarraySum(int[] nums, int k) {
        // 想要统计 i-j之间的个数 使用双层的for循环就可以解决
        int count = 0, pre = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i]; // 求前缀和      如果存在pre-k 那么就要加上
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    //https://leetcode.cn/problems/single-number/?envType=study-plan-v2&envId=top-100-liked
    public int singleNumber(int[] nums) {
        //任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
        //任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
        //异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
       //这个关键是 如何在o1的时间复杂度里面 找到唯一的数字
        int res=0;
        for (int i = 0; i <nums.length; i++) {
            res^=nums[i];
        }
        return res;
    }

    //最长的公共前缀  假设第一个是最长的，从后面往前进行比较,不断缩减第一个的长度
    //直到末尾元素  如果这个长度直接为0了 说明没有公共前缀的了
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0){
            return "";
        }
        String strMax=strs[0];
        for (int i = 0; i < strs.length; i++) {
            String str=strs[i];
            // 缩减strMax的长度
            while (str.indexOf(strMax)!=0){
                strMax=strMax.substring(0,strMax.length()-1);
                if (strMax.isEmpty()){
                    return "";
                }
            }
        }
        return strMax;
    }

}
